package org.forever.util
{
	/**
	* 基于双向链表实现序列
	*/
	public class Sequence_DLNode extends List_DLNode implements Sequence
	{
		public function Sequence_DLNode()
		{
			super();
		}
		
		/**检查秩r是否在[0, n)之间*/
		protected function checkRank(r:int,n:int):void {
			if (r < 0 || r >= n)
				throw new Error("意外：非法的秩" + r + "，应该属于[0, " + n +")");
		}
		
		/**若0 <= r < getSize()，则返回秩为r的元素所在的位置；否则，报错--O(n)*/
	    public function rank2Pos(r:int):Position {
			var node:DLNode = null;
			checkRank(r, getSize());
			if (r <= getSize()/2) {//若秩较小，则
				node = _header.getNext();//从前端开始
				for (var i:int=0; i<r; i++)	{
					node = node.getNext();//逐一扫描
				}
			} else {//若秩较大，则
				node = _trailer.getPrev();//从后端开始
				for (var j:int=1; j<getSize()-r; j++)	{
					node = node.getPrev();//逐一扫描
				}
			}
			return node;
		}
		
		public function pos2Rank(p:Position):int{
			var node:DLNode = _header.getNext();
			var r:int = 0;
			while (node != _trailer) {
				if (node == p)	return(r);
				node = node.getNext();	r++;
			}
			throw new Error("意外：作为参数的位置不属于序列");
		}
		
		/**取秩为r的元素--O(n)*/
		public function getAtRank(r:int):Object {
			checkRank(r, getSize());
			return rank2Pos(r).getElem();
		}
		
		/**将秩为r的元素替换为obj--O(n)*/
		public function replaceAtRank(r:int,obj:Object) :Object {
			checkRank(r, getSize());
			return replace(rank2Pos(r), obj);
		}
		
		/**插入obj，作为秩为r的元素--O(n)；返回该元素*/
		public function insertAtRank(r:int, obj:Object):Object {
			checkRank(r, getSize()+1);
			if (getSize() == r)	insertLast(obj);
			else insertBefore(rank2Pos(r), obj);
			return obj;
		}
		
		/**删除秩为r的元素--O(n)*/
		public function removeAtRank(r:int):Object {
			checkRank(r, getSize());
			return remove(rank2Pos(r));
		}
		
	}
}